##cvxopt.solvers模块求解
#min1/2*(xT)*P*x+(qT)*x
#s.t.Ax<=b
#Aeq*x=beq

# import numpy as np
# from cvxopt import matrix, solvers
# n=3;P=matrix(0.,(n,n))
# P[::n+1]=[3,2,1.7]#切片赋值，从头到尾，步长为n+3
# q=matrix([3,-8.2,-1.95])
# A = matrix([[1.,0,1],[ -1,2,0],[0,1,2]]).T
# b=matrix([2.,2,3])
# Aeq=matrix(1.,(1,n));beq=matrix(3.)
# s= solvers.qp(P,q, A, b, Aeq, beq)
# print('最优解为：',s['x'])
# print('最优值为：',s['primal objective'])



# import numpy as np
# # 给定数据点
# x = np.array([0, 1, 2])
# y = np.array([1, 2, 4])
#
# # 计算各项和
# n = len(x)
# sum_x = np.sum(x)
# sum_y = np.sum(y)
# sum_xy = np.sum(x * y)
# sum_x2 = np.sum(x ** 2)
#
# # 计算斜率a和截距b
# a = (n * sum_xy - sum_x * sum_y) / (n * sum_x2 - sum_x ** 2)
# b = (sum_y - a * sum_x) / n
#
# print(f"拟合的线性函数为: f(x) = {a:.2f}x + {b:.2f}")
#
# # 使用numpy的polyfit验证结果
# coefficients = np.polyfit(x, y, 1)
# print(f"使用numpy验证结果: f(x) = {coefficients[0]:.2f}x + {coefficients[1]:.2f}")

import numpy as np
from collections import defaultdict
# 定义数据点
points = {
    'X1': np.array([2, 10]),
    'X2': np.array([2, 5]),
    'X3': np.array([8, 4]),
    'X4': np.array([5, 8]),
    'X5': np.array([7, 5]),
    'X6': np.array([6, 4]),
    'X7': np.array([1, 2]),
    'X8': np.array([4, 9])
}
# 初始化中心点
centers = {
    'C1': points['X1'],
    'C2': points['X4'],
    'C3': points['X7']
}


def euclidean_distance(a, b):
    # 计算欧几里得距离的平方（简化计算）
    return np.sum((a - b) ** 2)

def k_means(points, centers, max_iterations=100):
    for _ in range(max_iterations):
        # 分配步骤：将每个点分配到最近的中心
        clusters = defaultdict(list)
        for name, point in points.items():
            # 计算点到每个中心的距离
            distances = {
                c_name: euclidean_distance(point, c_point)
                for c_name, c_point in centers.items()
            }
            # 找到最近的中心
            closest = min(distances.items(), key=lambda x: x[1])[0]
            clusters[closest].append(name)

        # 更新步骤：重新计算中心点
        new_centers = {}
        for c_name, members in clusters.items():
            # 计算簇内所有点的均值作为新中心
            member_points = [points[name] for name in members]
            new_center = np.mean(member_points, axis=0)
            new_centers[c_name] = new_center

        # 检查中心点是否变化
        if all(np.array_equal(centers[c], new_centers[c]) for c in centers):
            break

        centers = new_centers

    return clusters, centers

# 运行K-means算法
final_clusters, final_centers = k_means(points, centers)

# 打印结果
print("最终聚类结果：")
for cluster, members in final_clusters.items():
    print(f"{cluster}: {', '.join(members)}")
    print(f"中心点位置: {final_centers[cluster]}")

print("\n各点最终分配：")
for point in points:
    for cluster, members in final_clusters.items():
        if point in members:
            print(f"{point} -> {cluster}")
            break